package solution._0030._0030;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * Created by chen_snow
 * Date: 2021/5/17 23:45
 * Description: 串联所有单词的子串
 */
public class Solution {

    public static ArrayList<Integer> result = new ArrayList<>();
    public static HashMap<String, Integer> dataMap = new HashMap<>();

    public static void main(String[] args) {
        System.out.println(findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"}));
    }

    public static List<Integer> findSubstring(String s, String[] words) {

        Arrays.stream(words).forEach(word -> {
            dataMap.compute(word, (key, value) -> (value == null ? 1 : value + 1));
        });

        int length = words[0].length();

        for (int i = 0; i < words[0].length(); i++) {
            // 每次移动word长度
            count(s, i, words.length, length, new HashMap<String, Integer>());
        }

        return result;
    }

    public static void count(String s, int index, int num, int length, HashMap<String, Integer> data) {
        int start = index;
        int n = 0;

        while (index <= s.length() - length * num) {

            while (n < num) {
                if (start + length > s.length()) {
                    return;
                }

                String key = s.substring(start, start + length);

                if (dataMap.containsKey(key)) {
                    // 如果key的次数未满，则放入map中
                    Integer value = data.getOrDefault(key, 0);
                    if (value < dataMap.get(key)) {
                        data.put(key, value + 1);
                        start += length;
                        n++;
                    } else {
                        // 如果key的次数已满，剔除第一个key出现位置之前所有的字符串，包括第一个key
                        String str = s.substring(index, index + length);
                        while (!str.equals(key)) {
                            data.computeIfPresent(str, (k, v) -> (--v));
                            n--;
                            index += length;
                            str = s.substring(index, index + length);
                        }

                        data.computeIfPresent(str, (k, v) -> (--v));
                        n--;
                        index += length;

                    }

                } else {
                    // 如果key不存在，则需要剔除key前面所有依据统计的字符串
                    while (index < start) {
                        String str = s.substring(index, index + length);
                        data.computeIfPresent(str, (k, v) -> (--v));
                        index += length;
                        n--;
                    }
                    index += length;
                    start = index;
                }
            }

            result.add(index);
            String str = s.substring(index, index + length);
            data.computeIfPresent(str, (k, v) -> (--v));
            n--;
            index += length;
        }
    }
}
